package com.cty._04_Optimization._43_NumberOf1;

/**
 * @Auther: cty
 * @Date: 2020/7/17 12:29
 * @Description: 面试题43：从1到n整数中1出现的次数
 * 题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如
 * 输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。
 * @version: 1.0
 */
public class NumberOf1 {

    /**
     * 方法一：按各位中1出现的规律分析
     * 时间复杂度：O(logN)
     * @param n
     * @return
     */
    public static int numberOf1(int n){
        String nStr = new Integer(n).toString();
        int length = nStr.length();

        int first = nStr.charAt(0) - '0';
        if(length==1 && first==0)  // 0
            return 0;
        if(length==1 && first>0)  // 1-9
            return 1;

        // length > 1 , 此时first不可能等于，假设n=21345
        // part1：最高位的1出现次数
        int numFirstDigit = 0;
        if(first > 1)
            numFirstDigit = (int)(Math.pow(10,length-1));
        else if(first == 1)
            numFirstDigit = Integer.parseInt(nStr.substring(1)) + 1;

        // part2：1346 ~ 21345 中1出现的次数（不算最高位为1的情况）
        int numOfOtherDigit = first*(length-1)*(int)(Math.pow(10,length-2));

        // part3：0 ~ 1345 中1出现的次数（递归）
        int numRecursive = numberOf1(Integer.parseInt(nStr.substring(1)));

        return numFirstDigit + numOfOtherDigit + numRecursive;
    }  // end numberOf1()


    /**
     * 方法二：遍历统计
     * 时间复杂度：O(N*logN)
     * @param n
     * @return
     */
    public static int numberOf1_2(int n){
        int numberOf1 = 0;

        for(int i=1; i<=n; i++){
            numberOf1 += numberOf1InN(i);
        }
        return numberOf1;
    }  // end numberOf1_2()

    private static int numberOf1InN(int n){
        int numberOf1InN = 0;
        while(n != 0){
            if(n%10 == 1)
                numberOf1InN++;
            n /= 10;
        }
        return numberOf1InN;
    }  // end NumberOf1InN()

}  // end class
